In general terms, a computer network is a collection of end systems (also known as nodes) interconnected through one or more communication links. Generally, the end systems both send data to other end systems on the network and receive data sent by other end systems on the network. When an end system is a sender of data, it is referred to as a source for that data; when it is a receiver of data, it is referred to as a destination for the data. Typically, end systems act as both sources and destinations depending on whether they are sending or receiving data. When acting as a source, the system typically sends data in the form of messages over a communication link. Messages can flow back and forth to other communication links and end systems within the network through bridges or routers, which are used to interconnect multiple communication links.
Each message comprises a sequence of bits. Typically, messages sent over a network are divided up into smaller blocks of information called packets. The flow of packets in the network is usually referred to as traffic. An important design objective in networks is controlling traffic so that individual packets will not be transmitted at a faster rate than they can be processed by the communication links, or intermediate systems such as bridges or routers, through which the packets will pass, or by the destinations.
Asynchronous transfer mode (ATM) is one of the general class of digital switching technologies that relay and route traffic by means of a virtual circuit identifier (VCI) contained within the cell. Unlike common packet technologies, such as X.25 or frame relay, ATM uses very short, fixed length units of information, called cells. In applications utilizing ATM, packets at a source are first broken up into these fixed length packets (ATM cells), transmitted, and then reassembled at a destination. ATM cells are 53 bytes long. They consist of a 5-byte header (containing an identifier of data flow which implicitly identifies the source address and the destination address) and a 48-byte information field. The header of an ATM cell contains all the information the network needs to relay the cell from one node to the next over a pre-established route. User data is contained in the remaining 48 bytes.
ATM uses a concept of virtual networking (or channels) to pass traffic between two locations, establishing virtual connections between a pair of ATM end-systems which are needed to connect a source with a destination. These connections are termed "virtual" to distinguish them from dedicated circuits. ATM cells always traverse the same path from source to destination. However, ATM does not have to reserve the path for one user exclusively. Any time a given user is not occupying a link, another user is free to use it.
ATM connections exist only as sets of routing tables held in each network node, switch, or other intermediate system, based on the virtual circuit identifier (VCI) and virtual path identifier (VPI) contained in the cell header. When a virtual path is established, each node (or switch) is provided with a set of lookup tables that identify an incoming cell by header address, route it through the node to the proper output port, and overwrite the incoming VCI/VPI with a new one that the next node along the route will recognize as an entry in its routing table.
The cell is thus passed from switch to switch over a prescribed route, but the route is "virtual" since the facility carrying the cell is dedicated to it only while the cell traverses it. Two cells that are ultimately headed for different destinations may be carried, one after the other, over the same physical wire for a common portion of their journey.
With ATM, the successful transmission of packets from a source to a destination requires successful delivery of all the ATM cells formed from the original information packet. If any one cell is lost, the entire packet must be re-transmitted again. When the ATM station repeatedly tries to resend the original information packet, the network becomes increasingly loaded as more network congestion occurs and more cells are lost. As a result, ATM networks can operate efficiently when there is no cell loss.
A common method of controlling traffic, also known as flow control, is called the credit-based, per hop, per virtual circuit (VC) flow control. This method allows the network links to operate near full capacity without cell loss or instability. ATM credit based flow control requires that a cell not be transmitted on a communication link unless the sender knows that a buffer is available at the receiver to hold the cell. The sender maintains a "credit balance" for each virtual circuit (VC). As cells are sent, the sender decrements the balance, and refrains from sending a new cell if the balance is zero. When the receiver forwards a cell (thereby freeing a buffer), it transmits to the sender a credit. The sender and receiver in hop by hop flow control are on either side of the communications link.
In ATM, the receiver adapter at the end of a vitual circuit (VC) can be in a state where it reassembles in its local memory a large amount of packets at the same time. The reassembled packets can be as large as 64K bytes. For implementations where the adapter frees up its local memory only when the packet reassembly has been finished, there is a need for a large local memory. The reason for this is that the adapter should be able to simultaneously reassemble X packets, where X may be the number of all of its virtual circuits it supports simulataneously.
If the adapter has a smaller local memory and uses credit-based flow control to stop the senders from overflowing its local memory, "deadlock" may occur. This deadlock will be caused by the fact that the adapter, when beginning to become congested, will stop returning credits to the senders, and not free up its local memory because packets have not been completely reassembled. In addition, the senders will not attempt to send the last cells for the packet because they have no more credits to transmit new cells.
One problem with this is that, if the adapter has to support a very large number of open virtual circuits, very large local memory will be required.
A common approach to this problem is to reduce the number of supported receive virtual circuits. A problem with this approach is that it limits the maximum number of connections that can be open at the same time, thus degrading overall network performance.
A method of using credit-based flow control in such a way that the adapter can support a large amount of open virtual circuits simultaneously without the requirement of a large local memory is needed.